package com.cuz.daileetcode.bat100;

public class 二维数组上下左右四个方向走出递增序列最长的长度 {
    public static void main(String[] args) {
        int[][] ints = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 7}};
        System.out.println(solution1(ints));
        System.out.println(solution2(ints));
    }

    public static int solution1(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int ans = 1;
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                ans = Math.max(process(matrix, 1, row, col), ans);
            }
        }
        return ans;
    }

    /**
     * 以 matrix[startX][startY]开始，向上下左右四个方向走
     * 之前的长度是preLen，可以走出多长的路径
     *
     * @param matrix
     * @param preLen
     * @param startX
     * @param startY
     * @return
     */
    private static int process(int[][] matrix, int preLen, int startX, int startY) {
        //如果位置越界说明到头了
        if (startX < 0 || startX >= matrix.length || startY < 0 || startY >= matrix[0].length) {
            return preLen;
        }
        int curIndexValue = matrix[startX][startY];
        int ans = preLen;
        if (outBoundReturnMin(matrix, startX + 1, startY) > curIndexValue) {
            ans = Math.max(process(matrix, preLen + 1, startX + 1, startY), ans);
        }
        if (outBoundReturnMin(matrix, startX - 1, startY) > curIndexValue) {
            ans = Math.max(process(matrix, preLen + 1, startX - 1, startY), ans);
        }
        if (outBoundReturnMin(matrix, startX, startY + 1) > curIndexValue) {
            ans = Math.max(process(matrix, preLen + 1, startX, startY + 1), ans);
        }
        if (outBoundReturnMin(matrix, startX, startY - 1) > curIndexValue) {
            ans = Math.max(process(matrix, preLen + 1, startX, startY - 1), ans);
        }
        return ans;
    }

    private static int outBoundReturnMin(int[][] matrix, int startX, int startY) {
        if (startX < 0 || startX >= matrix.length || startY < 0 || startY >= matrix[0].length) {
            return Integer.MIN_VALUE;
        }
        return matrix[startX][startY];
    }


    public static int solution2(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int ans = 1;
        int[][] memory = new int[matrix.length][matrix[0].length];
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                memory[row][col] = -1;
            }
        }
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                ans = Math.max(process2(matrix, 1, row, col, memory), ans);
            }
        }
        return ans;
    }

    /**
     * 以 matrix[startX][startY]开始，向上下左右四个方向走
     * 之前的长度是preLen，可以走出多长的路径
     *
     * @param matrix
     * @param preLen
     * @param startX
     * @param startY
     * @return
     */
    private static int process2(int[][] matrix, int preLen, int startX, int startY, int[][] memory) {
        //如果位置越界说明到头了
        if (startX < 0 || startX >= matrix.length || startY < 0 || startY >= matrix[0].length) {
            return preLen;
        }
        int ans = preLen;
        if (memory[startX][startY] != -1) {
            ans += memory[startX][startY];
        } else {
            int curIndexValue = matrix[startX][startY];
            if (outBoundReturnMin(matrix, startX + 1, startY) > curIndexValue) {
                ans = Math.max(process(matrix, preLen + 1, startX + 1, startY), ans);
            }
            if (outBoundReturnMin(matrix, startX - 1, startY) > curIndexValue) {
                ans = Math.max(process(matrix, preLen + 1, startX - 1, startY), ans);
            }
            if (outBoundReturnMin(matrix, startX, startY + 1) > curIndexValue) {
                ans = Math.max(process(matrix, preLen + 1, startX, startY + 1), ans);
            }
            if (outBoundReturnMin(matrix, startX, startY - 1) > curIndexValue) {
                ans = Math.max(process(matrix, preLen + 1, startX, startY - 1), ans);
            }
        }
        memory[startX][startY] = ans;
        return ans;
    }

}
